{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Koko Eating Bananas"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #binary-search"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #二分查找"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minEatingSpeed"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #爱吃香蕉的珂珂"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>珂珂喜欢吃香蕉。这里有 <code>n</code> 堆香蕉，第 <code>i</code> 堆中有&nbsp;<code>piles[i]</code>&nbsp;根香蕉。警卫已经离开了，将在 <code>h</code> 小时后回来。</p>\n",
    "\n",
    "<p>珂珂可以决定她吃香蕉的速度 <code>k</code> （单位：根/小时）。每个小时，她将会选择一堆香蕉，从中吃掉 <code>k</code> 根。如果这堆香蕉少于 <code>k</code> 根，她将吃掉这堆的所有香蕉，然后这一小时内不会再吃更多的香蕉。&nbsp;&nbsp;</p>\n",
    "\n",
    "<p>珂珂喜欢慢慢吃，但仍然想在警卫回来前吃掉所有的香蕉。</p>\n",
    "\n",
    "<p>返回她可以在 <code>h</code> 小时内吃掉所有香蕉的最小速度 <code>k</code>（<code>k</code> 为整数）。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<ul>\n",
    "</ul>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>piles = [3,6,7,11], h = 8\n",
    "<strong>输出：</strong>4\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>piles = [30,11,23,4,20], h = 5\n",
    "<strong>输出：</strong>30\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>piles = [30,11,23,4,20], h = 6\n",
    "<strong>输出：</strong>23\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= piles.length &lt;= 10<sup>4</sup></code></li>\n",
    "\t<li><code>piles.length &lt;= h &lt;= 10<sup>9</sup></code></li>\n",
    "\t<li><code>1 &lt;= piles[i] &lt;= 10<sup>9</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [koko-eating-bananas](https://leetcode.cn/problems/koko-eating-bananas/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [koko-eating-bananas](https://leetcode.cn/problems/koko-eating-bananas/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[3,6,7,11]\\n8', '[30,11,23,4,20]\\n5', '[30,11,23,4,20]\\n6']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minEatingSpeed(self, piles: List[int], h: int) -> int:\n",
    "        \n",
    "        def f(x, piles):\n",
    "            tm = 0\n",
    "            for p in piles:\n",
    "                tm += p//x\n",
    "                if p%x != 0:\n",
    "                    tm += 1\n",
    "            return tm\n",
    "        \n",
    "        l, r = 1, 10**9+1\n",
    "        while l < r:\n",
    "            mid = (l+r)//2\n",
    "            if f(mid, piles) == h:\n",
    "                r = mid\n",
    "            elif f(mid, piles) < h:\n",
    "                r = mid\n",
    "            else:\n",
    "                l = mid+1\n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minEatingSpeed(self, piles, H):\n",
    "        \"\"\"\n",
    "        :type piles: List[int]\n",
    "        :type H: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        lo, hi = 1, max(piles)\n",
    "        while lo < hi:\n",
    "            tmp = 0\n",
    "            mid = (lo + hi) // 2\n",
    "            for i in piles:\n",
    "                tmp += i // mid\n",
    "                if i % mid:\n",
    "                    tmp += 1\n",
    "            if tmp <= H:\n",
    "                hi = mid\n",
    "            else:\n",
    "                lo = mid + 1\n",
    "        return lo\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minEatingSpeed(self, piles, H):\n",
    "        \"\"\"\n",
    "        :type piles: List[int]\n",
    "        :type H: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        from math import ceil\n",
    "        \n",
    "        low,upper = ceil(sum(piles)/H), max(piles)\n",
    "        while low < upper:\n",
    "            mid = (low+upper)//2\n",
    "            t = sum([ceil(pile/mid) for pile in piles])\n",
    "            if t > H:\n",
    "                low = mid+1\n",
    "            else:\n",
    "                upper = mid\n",
    "        return low\n",
    "        \n",
    "        \"\"\"\n",
    "        k = math.ceil(sum(piles)/H)\n",
    "        i = k\n",
    "        while i >= k:\n",
    "            h = sum([math.ceil(x/i) for x in piles])\n",
    "            if h <= H:\n",
    "                return i\n",
    "            i += 1\n",
    "        \"\"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minEatingSpeed(self, piles, H):\n",
    "        \"\"\"\n",
    "        :type piles: List[int]\n",
    "        :type H: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        def isOK(K):  # 判断当前值，是否满足要求\n",
    "            return sum((p-1)//K + 1 for p in piles) <= H\n",
    "        l=1\n",
    "        r=max(piles)\n",
    "        while l<r:\n",
    "            mid=(l+r)//2\n",
    "            if not isOK(mid):\n",
    "                l = mid +1\n",
    "            else:\n",
    "                r = mid\n",
    "        return r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minEatingSpeed(self, piles, H):\n",
    "        \"\"\"\n",
    "        :type piles: List[int]\n",
    "        :type H: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        l = sum(piles) // H if sum(piles) % H == 0 else sum(piles) // H + 1\n",
    "        r = max(piles)\n",
    "        while r > l + 1:\n",
    "            m = (l + r) // 2\n",
    "            t = sum([x // m if x % m == 0 else x // m + 1 for x in piles])\n",
    "            if t > H:\n",
    "                l = m\n",
    "            else:\n",
    "                r = m\n",
    "        if sum([x // l if x % l == 0 else x // l + 1 for x in piles]) <= H:\n",
    "            return l\n",
    "        else:\n",
    "            return r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minEatingSpeed(self, piles, H):\n",
    "        \"\"\"\n",
    "        :type piles: List[int]\n",
    "        :type H: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        a,b=1,max(piles)\n",
    "        while(1):\n",
    "            if a==b:\n",
    "                return a\n",
    "            c=int((a+b)/2)\n",
    "            if self.next(piles,c)<=H:\n",
    "                b=c\n",
    "            else:\n",
    "                a=c+1\n",
    "    def next(self,piles,K):\n",
    "        result=sum([self.cut(p,K) for p in piles])\n",
    "        print(K,result)\n",
    "        return result\n",
    "    def cut(self,a,b):\n",
    "        return a//b+(0 if a%b==0 else 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minEatingSpeed(self, piles: List[int], H: int) -> int:\n",
    "        if len(piles) == H:\n",
    "            return max(piles)\n",
    "        ans = (sum(piles) + H - 1)//H\n",
    "        while True:\n",
    "            h = sum((p+ans-1)//ans for p in piles)\n",
    "            if h <= H:\n",
    "                break\n",
    "            else:\n",
    "                ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minEatingSpeed(self, piles: List[int], H: int) -> int:\n",
    "        ans = (sum(piles) + H - 1)//H\n",
    "        while sum((p+ans-1)//ans for p in piles) > H:\n",
    "            ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minEatingSpeed(self, piles: List[int], H: int) -> int:\n",
    "        def possible(K):\n",
    "            return sum(math.ceil(p/K) for p in piles) <= H\n",
    "        \n",
    "        # 二分查找K\n",
    "        lo, hi = 1, max(piles)\n",
    "        while(lo<hi):\n",
    "            mid = (lo+hi)//2\n",
    "            if not possible(mid):\n",
    "                lo = mid + 1\n",
    "            else:\n",
    "                hi = mid\n",
    "        return lo\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minEatingSpeed(self, piles: List[int], H: int) -> int:\n",
    "        def judge(piles,k):\n",
    "            tmp = 0\n",
    "            for num in piles:\n",
    "                if num%k>0:\n",
    "                    tmp = tmp + (num//k)+1\n",
    "                else:\n",
    "                    tmp += num//k\n",
    "            return tmp\n",
    "        left = 1\n",
    "        right = max(piles)\n",
    "        while left<right:\n",
    "            mid = (left+right)//2\n",
    "            if judge(piles,mid)>H:#说明吃快了\n",
    "                left = mid+1\n",
    "            else:\n",
    "                right = mid\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minEatingSpeed(self, piles: List[int], H: int) -> int:\n",
    "        def judge(piles, k):\n",
    "            res = 0\n",
    "            for num in piles:\n",
    "                res = res + (num+k-1)//k\n",
    "            return res\n",
    "        left, right = 1, max(piles)\n",
    "\n",
    "        while left < right:\n",
    "            mid = (left + right) // 2\n",
    "            temp = judge(piles, mid)\n",
    "            if temp > H:\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid\n",
    "        return left\n",
    "\n",
    "class Solution:\n",
    "    def minEatingSpeed(self, piles: List[int], H: int) -> int:\n",
    "        def judge(piles, k):\n",
    "            res = 0\n",
    "            for num in piles:\n",
    "                res = res + (num + k - 1)//k\n",
    "            return res\n",
    "\n",
    "        minn, maxn = min(piles), max(piles)\n",
    "        if judge(piles, minn) > H:\n",
    "            left, right = minn, maxn\n",
    "        else:\n",
    "            left, right = 1, minn\n",
    "       \n",
    "\n",
    "        while left < right:\n",
    "            mid = (left + right) // 2\n",
    "            if judge(piles, mid) > H:\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    # def minEatingSpeed(self, piles: List[int], H: int) -> int:\n",
    "    def minEatingSpeed(self, piles, H: int) -> int:\n",
    "        left = 1\n",
    "        right = max(piles)\n",
    "        \n",
    "        while left < right:\n",
    "            mid = (left + right) >> 1\n",
    "            \n",
    "            if self.can_eat(piles, H, mid):\n",
    "                right = mid\n",
    "            else:\n",
    "                left = mid + 1\n",
    "                \n",
    "        return left\n",
    "            \n",
    "    def can_eat(self, piles, H, speed):\n",
    "        for pile in piles:\n",
    "            H -= math.ceil(pile / speed)\n",
    "            \n",
    "        return True if H >= 0 else False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minEatingSpeed(self, piles: List[int], H: int) -> int:\n",
    "        def possible_index(val):\n",
    "            return sum((pile-1)//val +1 for pile in piles) <= H\n",
    "        max_piles = max(piles)\n",
    "        left, right = 1, max_piles\n",
    "        while left<right:\n",
    "            mid_val = (left + right) // 2\n",
    "            if not possible_index(mid_val):\n",
    "                left = mid_val + 1\n",
    "            else:\n",
    "                right = mid_val\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\tdef minEatingSpeed(self, piles, H: int) -> int:\n",
    "\t\tpiles.sort()\n",
    "\t\tlength = len(piles)\n",
    "\t\tif length == H:\n",
    "\t\t\treturn piles[length - 1]\n",
    "\t\tif sum(piles) <= H:\n",
    "\t\t\treturn 1\n",
    "\t\ti = None\n",
    "\t\tfor tmp_i in range(length):\n",
    "\t\t\tflag = 0\n",
    "\t\t\ttmp_h = 0\n",
    "\t\t\tfor j in range(length):\n",
    "\t\t\t\tif piles[j] % piles[tmp_i] > 0:\n",
    "\t\t\t\t\ttmp_h += piles[j] // piles[tmp_i] + 1\n",
    "\t\t\t\telse:\n",
    "\t\t\t\t\ttmp_h += piles[j] // piles[tmp_i]\n",
    "\t\t\tif tmp_h <= H:\n",
    "\t\t\t\ti = tmp_i\n",
    "\t\t\t\tbreak\n",
    "\t\tspeed_max = piles[i]\n",
    "\t\tleft = piles[i - 1] if i > 0 else 0\n",
    "\t\tright = piles[i]\n",
    "\t\tmid = (left + right) // 2\n",
    "\t\tres = mid\n",
    "\t\tlast_h = None\n",
    "\t\twhile True:\n",
    "\t\t\tres = mid\n",
    "\t\t\ttmp_h = 0\n",
    "\t\t\tfor j in range(length):\n",
    "\t\t\t\tif piles[j] % mid > 0:\n",
    "\t\t\t\t\ttmp_h += piles[j] // mid + 1\n",
    "\t\t\t\telse:\n",
    "\t\t\t\t\ttmp_h += piles[j] // mid\n",
    "\t\t\tif left == right - 1:\n",
    "\t\t\t\tif tmp_h > H:\n",
    "\t\t\t\t\treturn right\n",
    "\t\t\t\telse:\n",
    "\t\t\t\t\treturn left\n",
    "\t\t\tif tmp_h > H:\n",
    "\t\t\t\tleft = mid\n",
    "\t\t\t\tmid = (left + right) // 2\n",
    "\t\t\telif tmp_h <= H:\n",
    "\t\t\t\tright = mid\n",
    "\t\t\t\tmid = (left + right) // 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def help(self,mid,piles,h):\n",
    "        time=0\n",
    "        for item in piles:\n",
    "            time=time+math.ceil(item/mid)\n",
    "        return time<=h\n",
    "    def minEatingSpeed(self, piles: List[int], h: int) -> int:\n",
    "        l=1\n",
    "        r=max(piles)\n",
    "        while l<=r:\n",
    "            mid=(l+r)//2\n",
    "            # num = 0\n",
    "            # for j in piles:\n",
    "            #     num = num + math.ceil(j / mid)\n",
    "            if self.help(mid,piles,h):\n",
    "            #if num<=h:\n",
    "                r=mid-1\n",
    "            else:\n",
    "                l=mid+1\n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "\n",
    "\n",
    "def how_many_hours(piles, speed):\n",
    "    days = 0\n",
    "    for i in piles:\n",
    "        days += math.ceil(i / speed)\n",
    "    return days\n",
    "\n",
    "\n",
    "def eat_bananas(piles, h):\n",
    "    start, end = 1, max(piles)\n",
    "    res = h\n",
    "    while start <= end:\n",
    "        speed = start + (end-start) // 2\n",
    "        hours = how_many_hours(piles, speed)\n",
    "        if hours > h:\n",
    "            start = speed + 1\n",
    "        else:  # hours <= h\n",
    "            res = speed\n",
    "            end = speed - 1\n",
    "    return res\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minEatingSpeed(self, piles: List[int], H: int) -> int:\n",
    "        return eat_bananas(piles, H)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# every time koko will eat min(k, piles[i])\n",
    "# if the length of piles == h, the minimun k is the max of piles\n",
    "# else, low = 1, high = piles[-1], every time k = mid can finish eat or not\n",
    "# time O(log(max(piles))+n+n)->log(max(piles)) is to binary search to find the k, n is the check function, 可以不排序，用n的时间来找max就行了，只需要max\n",
    "# space O(1)\n",
    "\n",
    "class Solution:\n",
    "    def minEatingSpeed(self, piles: List[int], h: int) -> int:\n",
    "        Max = max(piles)\n",
    "        if len(piles) == h:\n",
    "            return Max\n",
    "        low = Max // h\n",
    "        high = Max\n",
    "        while low <= high:\n",
    "            mid = (low + high) // 2\n",
    "            if not self.check(piles, mid, h):\n",
    "                low = mid + 1\n",
    "            else:\n",
    "                if mid == 1:\n",
    "                    return mid\n",
    "                if not self.check(piles, mid-1, h):\n",
    "                    return mid\n",
    "                high = mid - 1\n",
    "        return mid\n",
    "\n",
    "    def check(self, piles, k, h):\n",
    "        s = 0\n",
    "        for pile in piles:\n",
    "            if pile <= k:\n",
    "                s += 1\n",
    "            else:\n",
    "                s += (pile // k)\n",
    "                if pile % k > 0:\n",
    "                    s += 1\n",
    "        return s <= h"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minEatingSpeed(self, piles: List[int], h: int) -> int:\n",
    "        def minEatingSpeed(p: List[int], h: int) -> int:\n",
    "            \"\"\"\n",
    "            单纯用数学来做\n",
    "            \"\"\"\n",
    "\n",
    "            def charge_if_pass(k: int, p: List, h: int) -> int:\n",
    "                \"\"\"\n",
    "                检查是否可以通过，返回值是下一次需要增加到的数，最后一次返回直接是结果\n",
    "                \"\"\"\n",
    "                curr_sum_h = 0\n",
    "                next_k = 10 ** 1000  # 无穷大\n",
    "                for curr_p in p:\n",
    "                    cost = math.ceil(curr_p / k)\n",
    "                    if cost > 1:\n",
    "                        curr_need_k = math.ceil(curr_p / (cost - 1))\n",
    "                        next_k = min(next_k, curr_need_k)\n",
    "                    curr_sum_h += cost\n",
    "                if curr_sum_h <= h:\n",
    "                    return k\n",
    "                else:\n",
    "                    return charge_if_pass(next_k, p, h)\n",
    "\n",
    "            least_k = math.ceil(sum(p) / h)\n",
    "            return charge_if_pass(least_k, p, h)\n",
    "\n",
    "        return minEatingSpeed(piles, h)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minEatingSpeed(self, piles: List[int], h: int) -> int:\n",
    "        # 速度是mid  最小速度，也就是小于这个速度的话就吃不完了\n",
    "        def check(m):\n",
    "            ans = 0\n",
    "            for x in piles:\n",
    "                # t= ceil(x/m)\n",
    "                t = x//m if x%m==0 else x//m +1\n",
    "                ans += t\n",
    "            return ans <= h  # 说明没吃完，left右移\n",
    "        left = 1\n",
    "        right = max(piles)\n",
    "        while left <= right:\n",
    "            mid = left + (right-left)//2\n",
    "            if check(mid):\n",
    "                right = mid -1\n",
    "            else:\n",
    "                left = mid +1\n",
    "        return left\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minEatingSpeed(self, piles: List[int], h: int) -> int:\n",
    "        def minEatingSpeed(p: List[int], h: int) -> int:\n",
    "            \"\"\"\n",
    "            单纯用数学来做\n",
    "            \"\"\"\n",
    "\n",
    "            def charge_if_pass(k: int, p: List, h: int) -> int:\n",
    "                \"\"\"\n",
    "                检查是否可以通过，返回值是下一次需要增加到的数，最后一次返回直接是结果\n",
    "                \"\"\"\n",
    "                curr_sum_h = 0\n",
    "                next_k = 10 ** 1000  # 无穷大\n",
    "                after_list = []  # 剔除掉1天的\n",
    "                curr_need_h = 0  # 统计当前k速度下，至少消耗1天的，在下次递归直接剔除\n",
    "                for curr_p in p:\n",
    "                    cost = math.ceil(curr_p / k)\n",
    "                    if cost > 1:\n",
    "                        curr_need_k = math.ceil(curr_p / (cost - 1))\n",
    "                        next_k = min(next_k, curr_need_k)\n",
    "                        after_list.append(curr_p)\n",
    "                    else:\n",
    "                        curr_need_h += 1\n",
    "                    curr_sum_h += cost\n",
    "                if curr_sum_h <= h:\n",
    "                    return k\n",
    "                else:\n",
    "                    return charge_if_pass(next_k, after_list, h - curr_need_h)\n",
    "\n",
    "            least_k = math.ceil(sum(p) / h)\n",
    "            return charge_if_pass(least_k, p, h)\n",
    "\n",
    "        return minEatingSpeed(piles, h)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minEatingSpeed(self, piles: List[int], h: int) -> int:\n",
    "        left, right = 1, max(piles)\n",
    "        while left <= right:\n",
    "            mid = left + (right - left) // 2\n",
    "            needhours = sum(math.ceil(p / mid) for p in piles)\n",
    "            if needhours <= h:\n",
    "                right = mid - 1\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minEatingSpeed(self, piles: List[int], h: int) -> int:\n",
    "        # left, right 是每小时吃的香蕉个数的最小值和最大值\n",
    "        # 求最小速度，就是求最合适的left\n",
    "        left, right = 1, max(piles)\n",
    "        while left <= right:\n",
    "            mid = left + (right - left) // 2\n",
    "            hours = sum(math.ceil(pile / mid) for pile in piles)\n",
    "            if hours > h:\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid - 1\n",
    "        \n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minEatingSpeed(self, piles: List[int], h: int) -> int:\n",
    "        #times = []\n",
    "        left, right = 1,  max(piles)\n",
    "        #ans = float('inf')\n",
    "\n",
    "        while left <= right:\n",
    "            time = 0\n",
    "            mid = (left + right)//2\n",
    "            #print(left,right,mid)\n",
    "            for i in range(len(piles)):\n",
    "                time += math.ceil(piles[i]/mid)\n",
    "            #print(time,mid)\n",
    "            if time <= h:\n",
    "                #times.append(mid)\n",
    "                right = mid - 1\n",
    "                ans = mid\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        #print(times)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minEatingSpeed(self, piles: List[int], h: int) -> int:\n",
    "        #times = []\n",
    "        left, right = 1,  max(piles)\n",
    "        ans = float('inf')\n",
    "\n",
    "        while left <= right:\n",
    "            time = 0\n",
    "            mid = (left + right)//2\n",
    "            #print(left,right,mid)\n",
    "            for i in range(len(piles)):\n",
    "                time += math.ceil(piles[i]/mid)\n",
    "            #print(time,mid)\n",
    "            if time <= h:\n",
    "                #times.append(mid)\n",
    "                right = mid - 1\n",
    "                ans = min(ans, mid)\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        #print(times)\n",
    "        return ans"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
